#include "heap.h"
#define _CRT_SECURE_NO_WARNINGS 1
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void up(Heap* hp, int pos)
{
	if (pos / 2 >= 0 && hp->_a[pos] < hp->_a[pos / 2])
	{
		Swap(&hp->_a[pos], &hp->_a[pos / 2]);
		pos >>= 1;
	}
}
void HeapIni(Heap* hp)
{
	hp->_capacity = 0;
	hp->_size = 0;
	hp->_a = NULL;
}
void down(HPDataType* a, int pos, int end)
{
	if (pos * 2 + 1 >= end)
		return;
	int t = pos * 2 + 1;

	if (t + 1 < end && a[t] > a[t + 1])
		t++;

	if (a[t] < a[pos])
	{
		Swap(&a[t], &a[pos]);
		down(a, t, end);
	}

}
void HeapPush(Heap* hp, HPDataType x)
{
	if (hp->_size == hp->_capacity)
	{
		hp->_capacity = hp->_capacity == 0 ? 4 : 2 * hp->_capacity;
		hp->_a = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * hp->_capacity);
	}
	hp->_a[hp->_size] = x;

	up(hp,  hp->_size);

	hp->_size ++;
}

void HeapDestory(Heap* hp)
{
	free(hp->_a);
	hp->_capacity = 0;
	hp->_size = 0;
}


void HeapPop(Heap* hp)
{
	hp->_a[0] = hp->_a[hp->_size - 1];
	hp->_size--;
	down(hp->_a, 0, hp->_size);
}

HPDataType HeapTop(Heap* hp)
{
	return hp->_a[0];
}

int HeapSize(Heap* hp)
{
	return hp->_size;
}

int HeapEmpty(Heap* hp)
{
	return hp->_size == 0;
}
